#include <string>

#define PAGESIZE    16384   // 16KB
// 16-bit addr  +  16-bit size
typedef int RecordID;

typedef struct pagemgr_t {
    unsigned short total_size;      // total size of active record data
    unsigned short num_records;     // number of valid records
    unsigned short del_first;       // offset of deleted records;
    unsigned short addr_offset;     // total size of address pointers
    unsigned short record_first;    // addr of first record
    unsigned short record_last;     // addr of last record
    const char page[PAGESIZE];      // Page memory
} pagemgr_t;

typedef struct record_hdr_t {
    RecordID id;
    short int prev_offset;
    short int next_offset;
} record_hdr_t;

pagemgr_t pagemgr;

// called at the beginning of the program
void init() {
    memset(&pagemgr, 0, sizeof(pagemgr));
    pagemgr.del_first = 0xffff;
}

static unsigned short getaddr(unsigned short ridx)
{
    if (ridx<<1 + 2 > PAGESIZE) // invalid idx
        return;
    unsigned short *p = pagemgr.page + PAGESIZE - (ridx+1)*2;
    return *p;
}

static void setaddr(unsigned short ridx, unsigned short value)
{
    if (ridx<<1 + 2 > PAGESIZE) // invalid idx
        return;
    unsigned short *p = pagemgr.page + PAGESIZE - (ridx+1)*2;
    *p = value;
}

static void defrag_records()
{
    size_t n;
    record_hdr_t *rhdr = NULL;
    unsigned short offset, ridx, dest_offset = 0;

    do {
        assert(dest_offset <= offset);
        offset = (rhdr)?rhdr->next_offset:pagemgr.record_first;
        rhdr = (record_hdr_t *)(pagemgr.page + offset);
        n = (rhdr->id & 0x0000ffff) + sizeof(record_hdr_t);
        ridx = (rhdr->id >> 16);
        if (dest_offset < offset) {
            memmove((void *)(pagemgr.page + dest_offset),
                    (void *)(pagemgr.page + offset), n);
        }
        // update address table
        setaddr(ridx, dest_offset);
        // move on to next record
        dest_offset += n;
    } while (rhdr->next_offset > 0);

    // update pointer to last record
    pagemgr.record_last = offset;
}

RecordID AddRecord(string r)
{
    RecordID id;
    unsigned short offset;
    int size = r.size();
    record_hdr_t *prev_hdr, *cur_hdr;
    
    if (size <= 0 || size > PAGESIZE) return -1;
    
    // indeed run out of space
    if (pagemgr.total_size + size > PAGESIZE - pagemgr.addr_offset) {
        return -1;
    }
    
    cur_hdr = (record_hdr_t *)pagemgr.record_last;
    offset = pagemgr.record_last + sizeof(record_hdr_t) + (cur_hdr->id & 0x0000ffff);
    if (offset + sizeof(struct record_hdr) + size >
        PAGESIZE - pagemgr.addr_offset) {
        // compress free space to insert new record
        defrag_records();
    }
    cur_hdr = (record_hdr_t *)(pagemgr.page + pagemgr.record_last);
    offset = pagemgr.record_last + sizeof(record_hdr_t) + (cur_hdr->id & 0x0000ffff);

    unsigned short ridx;
    // find an empty slot in addr table or increase table size
    if (pagemgr.del_first != 0xffff &&
        (pagemgr.del_first+1)*2 < pagemgr.addr_offset)
    {
        ridx = pagemgr.del_first;
        pagemgr.del_first = getaddr(pagemgr.del_first) & ~(1<<15);
    } else {
        // increase addr table
        pagemgr.addr_offset += 2;
        ridx = pagemgr.add_offset/2 - 1;
        pagemgr.del_first = 0xffff;
    }
    
    // make up record id
    id = (ridx << 16) + size;
    // store record address into addr table
    setaddr(ridx, offset);

    // update linked list
    prev_hdr = cur_hdr;
    // make up record header and copy record data
    cur_hdr = (record_hdr_t *)(pagemgr.page + offset);
    cur_hdr->id = id;
    cur_hdr->prev_offset = pagemgr.record_last;
    cur_hdr->next_offset = 0xffff;
    prev_hdr->next_offset = pagemgr.record_last = offset;
    memcpy((void *)(pagemgr.page + offset + sizeof(record_hdr_t)),
        (const void *)r.c_str(), (size_t)size);
    
    pagemgr.total_size += size;
    num_records++;
    return id;
}

string GetRecord(RecordID id)
{
    int size = id & 0x0000ffff;
    unsigned short ridx = (id >> 16);
    unsigned short offset = getaddr(ridx);

    if (offset < 0 ||
        offset > PAGE_SIZE  ||
        size <= 0 ||
        offset + size > PAGE_SIZE) {
        // invalid id
        return NULL;
    }

    record_hdr_t *r_hdr = (record_hdr_t *)(pagemgr.page + offset);
    if (r_hdr->id != id) {
        // invalid record ID
        return NULL;
    }

    const char *r_start = pagemgr.page + offset + sizeof(record_hdr_t);
    string r(r_start, size);
    return r;
}

bool DelRecord(RecordID id)
{
    int size = id & 0x0000ffff;
    unsigned short ridx = (id >> 16);
    unsigned short offset = getaddr(ridx);

    if (!pagemgr.num_records) return false;
    if (offset < 0 ||
        offset > PAGE_SIZE  ||
        size <= 0 ||
        offset + size > PAGE_SIZE) {
        // invalid id
        return false;
    }

    if (ridx + 1 == pagemgr.addr_offset/2) {
        // if record with largest idx is deleted
        // reduce entire address range
        pagemgr.addr_offset -= 2;
    } else {
        setaddr(ridx, (pagemgr.del_first | (1<<15)));
        pagemgr.del_first = ridx;
    }

    // adjust linked list of allocated blocks
    record_hdr_t *r_hdr = (record_hdr_t *)(pagemgr.page + offset);
    record_hdr_t *prev_hdr = (record_hdr_t *)(pagemgr.page + r_hdr->prev_offset);
    record_hdr_t *next_hdr = (r_hdr->next_offset > 0)?
        (record_hdr_t *)(pagemgr.page + r_hdr->next_offset):NULL;
    prev_hdr->next_offset = r_hdr->next_offset;
    if (next_hdr)
        next_hdr->prev_offset = r_hdr->prev_offset;
    
    // update head of record list if first elem is deleted
    if (offset == pagemgr.record_first) {
        pagemgr.record_first = r_hdr->next_offset;
    }

    pagemgr.total_size -= size;
    pagemgr.num_records--;
    return true;
}
